package leetcode.slidewindow;

import java.util.*;

/**
 * 438. 找到字符串中所有字母异位词
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * <p>
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * 示例 2:
 * <p>
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 */
public class FindAnagrams1 {

    /**
     * 滑动窗口 模板
     */
    public void window() {
        int[] arr = new int[10];

        int left = 0;
        int right = 0;

        List<Integer> window = new ArrayList<>();

        while (right < arr.length) {

            // 增大窗口
            int rightVal = arr[right];
            window.add(rightVal);
            right++;

            while (true) {
                // 缩小窗口
                int leftVal = arr[left];
                window.remove(leftVal);
                left++;
            }
        }
    }

    /**
     * 推荐解法
     * <p>
     * 滑动窗口
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {

        char[] arr1 = s.toCharArray();
        char[] arr2 = p.toCharArray();
        List<Integer> ans = new ArrayList<>();



        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char c : arr2) {
            Integer num = need.getOrDefault(c, 0);
            need.put(c, num + 1);
        }

        int count = need.size();
        int actCount = 0;

        int left = 0;
        int right = 0;

        while (right < arr1.length) {

            char cur = arr1[right];

            window.put(cur, window.getOrDefault(cur, 0) + 1);
            if (window.get(cur) == need.get(cur)) {
                actCount++;
            }

            while (right - left >= arr2.length) {
                if (actCount == count) {
                    ans.add(left);
                }

                char leftVal = arr1[left];
                if (window.get(leftVal) == need.get(leftVal)) {
                    actCount--;
                }
                window.put(cur, window.get(cur) - 1);
                left++;
            }
        }
        return ans;
    }
}
